//class Solution {
//public:
//    int maxSubArray(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> dp(n + 1);
//        int ret = INT_MIN;
//        for (int i = 1; i <= n; i++)
//        {
//            dp[i] = max(dp[i - 1] + nums[i - 1], nums[i - 1]);
//            if (dp[i] > ret) ret = dp[i];
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    int maxSubarraySumCircular(vector<int>& nums) {
//        int n = nums.size();
//        int sum = 0;
//        for (auto& e : nums) sum += e;
//        vector<int> f(n + 1);
//        vector<int> g(n + 1);
//        int ret1 = INT_MIN;
//        int ret2 = INT_MAX;
//        for (int i = 1; i <= n; i++)
//        {
//            f[i] = max(nums[i - 1], f[i - 1] + nums[i - 1]);
//            if (f[i] > ret1) ret1 = f[i];
//        }
//        for (int i = 1; i <= n; i++)
//        {
//            g[i] = min(nums[i - 1], g[i - 1] + nums[i - 1]);
//            if (g[i] < ret2) ret2 = g[i];
//        }
//        if (sum == ret2) return ret1;
//        return max(ret1, sum - ret2);
//    }
//};

//class Solution {
//public:
//    int maxProduct(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n + 1);
//        vector<int> g(n + 1);
//        f[0] = 1;
//        g[0] = 1;
//        int ret = INT_MIN;
//        for (int i = 1; i <= n; i++)
//        {
//            int x = nums[i - 1], y = f[i - 1] * nums[i - 1], z = g[i - 1] * nums[i - 1];
//            f[i] = max(x, max(y, z));
//            g[i] = min(x, min(y, z));
//            if (f[i] > ret) ret = f[i];
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    int getMaxLen(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n + 1);
//        vector<int> g(n + 1);
//        int ret = INT_MIN;
//        for (int i = 1; i <= n; i++)
//        {
//            if (nums[i - 1] > 0)
//            {
//                f[i] = f[i - 1] + 1;
//                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
//            }
//            else if (nums[i - 1] < 0)
//            {
//                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
//                g[i] = f[i - 1] + 1;
//            }
//            if (f[i] > ret) ret = f[i];
//        }
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    int numberOfArithmeticSlices(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 1 || n == 2) return 0;
//        vector<int> dp(n);
//        for (int i = 2; i < n; i++)
//        {
//            dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
//        }
//        int ret = 0;
//        for (auto& e : dp) ret += e;
//        return ret;
//    }
//};

